package Top_Interview_Questions.Bit_Manipulation;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/31 20:33
 * <p>
 * 功能描述:
 */
public class _0169 {

    public static void main(String[] args) {
        _0169 test = new _0169();
        int[] nums = {2,2,1,1,1,2,2};
        System.out.println(test.majorityElement1(nums));
    }


    /**
     * 按理来说:hash表的时间复杂度是O(n)比这个排序的O(NlogN)快。但是实际上这个排序打败了%88,
     * hash表打败了%12.....。很疑惑，可能是数据规模问题
     */
    public int majorityElement3(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }



    /*-------------------------------------hash表---------------------------------------------*/
    /**
     * 输入: [2,2,1,1,1,2,2]
     * 输出: 2
     */
    public int majorityElement1(int[] nums) {
        int len = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer k : nums) {
            Integer count = map.get(k);
            count = count == null ? 1 : ++count;
            map.put(k,count);
        }
        for (Integer i : map.keySet()) {
            Integer count = map.get(i);
            if (count > len/2) {
                return i;
            }
        }
        return -1;
    }
    /*---------------------------------------------------------------------------------------*/
}
